package com.dateConstruction._02_sortedSinglyLinkedList;

import com.dateConstruction._02_singlyLinkedList.Node;
import com.dateConstruction._02_singlyLinkedList.SinglyLinkedList;

// 排序单链表类，继承单链表类；增加成员变量asc指定排序次序，升序或降序
// T或T的某个祖先类"?"实现Comparable<?>接口，提供compareTo()方法比较对象大小和相等
    
public class SortedSinglyLinkedList<T extends Comparable<? super T>> extends SinglyLinkedList<T> {
    
    // 排序次序，取值为true(升序)或false(降序)
    protected boolean asc;
    
    // 构造空排序单链表，默认升序
    public SortedSinglyLinkedList() {
        super();
    }
    
    // 构造方法，按值插入values数组元素
    public SortedSinglyLinkedList(T[] value, boolean asc) {
        super();
        this.asc = asc;
    }
    
    // 构造方法，按值插入values数组元素
    public SortedSinglyLinkedList(T[] value) {
        super();
        for (int i = 0; i < value.length; i++) {
            this.insert(value[i]);
        }
    }
    
    // 不支持父类的以下成员方法，将其覆盖并抛出异常
    // 排序单链表的数据元素具有只读特性，不支持写操作
    public void set(int i, T x) {
        throw new UnsupportedOperationException("set(int i, T x)");
    }
    
    // 不支持在指定位置插入
    public Node<T> insert(int i, T x) {
        throw new UnsupportedOperationException("insert(int i, T x)");
    }
    
    // 不支持直接首位合并连接，抛出异常
    public void concat(SinglyLinkedList<T> list) {
        throw new UnsupportedOperationException("concat(SinglyLinkedList<T> list)");
    }
    
    // 插入x，x != null，根据x对象大小顺序查找确定插入位置，插入在等值结点之后；返回插入结点
    // 由T类的compareTo()方法比较对象大小。覆盖父类insert(x)方法，参数列表和返回值相同
    public Node<T> insert(T x) {
        if (x == null) {
            return null;
        }
        Node<T> p = null;
        // 默认asc为false，升序x.compareTo(p.next.data) > 0时继续往后遍历再插入，逆序反之
        for (p = this.head; p.next != null && (asc == false ? x.compareTo(p.next.data) > 0 : x.compareTo(p.next.data) < 0); p = p.next);
        Node<T> q = new Node<T>(x, p.next);
        p.next = q;
        return q;
    }
    
    // 顺序查找并返回首个与key相等的元素
    public Node<T> search(T key) {
        if (key == null) {
            return null;
        }
        for (Node<T> p = this.head.next; p != null; p = p.next) {
            if (key.equals(p.data)) {
                return p;
            }
        }
        return null;
    }
    
    // 顺序查找，删除并返回首个与key相等的元素
    public T remove(T key) {
        if (key == null) {
            return null;
        }
        Node<T> front = null;
        for (front = this.head; front.next != null && !front.next.data.equals(key); front = front.next);
        T temp = front.next.data;
        front.next = front.next.next;
        return temp;
    }
    
    // 构造方法，调用父类的深拷贝，asc属性同list
    public SortedSinglyLinkedList(SortedSinglyLinkedList ssllist) {
        super(ssllist);
        this.asc = ssllist.asc;
    }
    
    // 构造方法，深拷贝，按值插入list所有元素
    public SortedSinglyLinkedList(SinglyLinkedList sslist, boolean asc) {
        this.asc = asc;
        for (Node<T> front = sslist.head.next; front != null; front = front.next) {
            insert(front.data);
        }
    }
    
    // 构造方法，深拷贝，由sslist单链表构造，默认升序
    public SortedSinglyLinkedList(SinglyLinkedList sslist) {
        for (Node<T> front = sslist.head.next; front != null; front = front.next) {
            insert(front.data);
        }
    }
    
    // 比较相等，其中算法先比较asc是否相同，在调用父类equals(Obj)方法，比较this与obj引用单链表是否相等
    public boolean equals(Object obj) {
        if (this == obj) {
            return true;
        }
        if (!(obj instanceof SortedSinglyLinkedList)) {
            return false;
        }
        SortedSinglyLinkedList<T> ssllist = (SortedSinglyLinkedList<T>) obj;
        if (ssllist.asc == this.asc) {
            return super.equals(ssllist);
        }
        return false;
    }
    
    // 集合并，this += list，复制list所有结点按值插入元素到this排序单链表中，不改变list
    public void addAll(SinglyLinkedList<T> list) {
        // 待写
    }
    
    // 返回并集(this + list)，即返回复制this和list所有结点的排序单链表，this和list不变，覆盖，返回值类型赋值相容
    public SinglyLinkedList<T> union(SinglyLinkedList<T> list) {
        // 待写
        return null;
    }
    
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Integer[] arr0 = {3, 1, 0, 2, 4, 6};
        SortedSinglyLinkedList<Integer> ssllist0 = new SortedSinglyLinkedList<Integer>(arr0);
        System.out.println("测试默认的升序数组构造(T[] value)：");
        System.out.println(ssllist0 + ", " + ssllist0.asc);
        System.out.println("测试insert(T x)方法：");
        System.out.println(ssllist0.insert((Integer)5) + ", " + ssllist0);
        System.out.println("测试search(T key)方法：");
        System.out.println(ssllist0.search((Integer)3));
        System.out.println("测试remove(T key)方法：");
        System.out.println(ssllist0.remove(2) + ", " + ssllist0);
        System.out.println("测试构造方法(SortedSinglyLinkedList ssllist)：");
        SortedSinglyLinkedList<Integer> ssllist1 = new SortedSinglyLinkedList<Integer>(ssllist0);
        System.out.println(ssllist1);
        System.out.println("测试构造方法(SinglyLinkedList sslist)：");
        SinglyLinkedList<Integer> sllist2 = new SinglyLinkedList<Integer>(arr0);
        SortedSinglyLinkedList<Integer> ssllist2 = new SortedSinglyLinkedList<Integer>(sllist2, true);
        System.out.println(ssllist2);
        System.out.println("测试equals(Object obj)：");
        System.out.println(ssllist0.equals(ssllist1));
        
    }

}
